package com.husd.leetcode.sort;

import java.util.Arrays;

/**
 * 1. 归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个典型的应用。
 * 它的基本操作是：将已有的子序列合并，达到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
 * 2. 归并排序其实要做两件事：
 * • 分解----将序列每次折半拆分
 * • 合并----将划分后的序列段两两排序合并 因此，归并排序实际上就是两个操作，拆分+合并
 * 1. 如何合并？ L[first...mid]为第一段，L[mid+1...last]为第二段，并且两端已经有序，
 * 现在我们要将两端合成达到L[first...last]并且也有序。
 * • 首先依次从第一段与第二段中取出元素比较，将较小的元素赋值给temp[]
 * • 重复执行上一步，当某一段赋值结束，则将另一段剩下的元素赋值给temp[]
 * • 此时将temp[]中的元素复制给L[]，则得到的L[first...last]有序
 * 如何分解？ 在这里，我们采用递归的方法，首先将待排序列分成A,B两组；然后重复对A、B序列 分组；
 * 直到分组后组内只有一个元素，此时我们认为组内所有元素有序，则分组结束。
 *
 * @author hushengdong
 */
public class MergeSort {

    //先拆分成2个，然后保证2个有序
    private static void sort(int[] a, int low, int high, int[] tmp) {

        if (low >= high) {
            return;
        }
        int mid = low + (high - low) / 2;
        sort(a, low, mid, tmp);
        sort(a, mid + 1, high, tmp);
        merge(a, low, mid, high, tmp);
    }

    private static void merge(int[] a, int low, int mid, int high, int[] tmp) {

        int l = low;
        int r = mid + 1;
        int inx = low;
        while (l <= mid && r <= high) {

            if (a[l] < a[r]) {
                tmp[inx++] = a[l++];
            } else {
                tmp[inx++] = a[r++];
            }
        }
        while (l <= mid) {
            tmp[inx++] = a[l++];
        }
        while (r <= high) {
            tmp[inx++] = a[r++];
        }
        //实际的长度应该是inx-1 inx是下一个值
        inx--;
        while (inx >= low) {
            a[inx] = tmp[inx];
            inx--;
        }
    }

    public static void main(String[] args) {

        int[] a = {5, 4, 3, 2, 10, 6, 7, 1, 8, 9, 18, -1, 29, -3, 30, -30};
        int[] tmp = new int[a.length];
        int n = a.length;
        MergeSort.sort(a, 0, n - 1, tmp);
        System.out.println(Arrays.toString(a));
    }
}
